PostgreSQL pg_trgm

#PostgreSQL #pg_trgm

1 背景知识

1、pg_trgm 扩展模块是根据三元组匹配算法确定文本的相似性，并提供模糊近似匹配的函数和索引运算符。
3、由于这个模块是信任级别，所以不需要超级管理员权限也能安装。

1.1 三元组概念

1、三元组是从字符串提取一组三个连续的字符，将每个字符添加两个前缀空格和一个后缀空格之后，称之为三元组。
2、所以一个字符串能够提取出多个三元组。
3、通过计算两个字符串相同的三元组来比较他们的相似度，这是在很多自然语言中非常简单高效的方法。
4、pg_trgm 扩展模块从字符串提取三元组时，会忽略非字母，非数字。

5、例如：字符串‘cat’中的三元组为：

"c"
"cat"
"at"

6、例如：字符串‘foo|bar’中的三元组为：

"f"
"fo"
"foo" 
"oo"
"b"
"ba" 
"bar" 
"ar"

1.2 三元组的函数

功能	描述
similarity ( text, ) → textreal	返回一个数字，表示两个字符串的相似程度。结果从0 到1。0 表示完全不同，1 表示完全相同。
show_trgm ( text ) → text[]	返回一个数组，表示字符串中所有的三元组。除了调试以外，很少有用。
word_similarity ( text, ) → textreal	返回一个数字，单词匹配模式下，表示两个字符串中的单词最大的相似性。
strict_word_similarity ( text, ) →textreal	返回一个数字，严格单词匹配模式下，表示两个字符串中的完全匹配单词的相似性。
show_limit() →real	显示两个字符串的相似性最低阈值，已弃用（请使用 SHOW pg_trgm.similarity_threshold）。
set_limit ( real ) → real	设置两个字符串的相似性最低阈值，已弃用（请使用 SET pg_trgm.similarity_threshold)。

1.3 pg_trgm 运算符

操作符	描述
text % text → boolean	字符串模式：两个字符串相似度超过 `pg_trgm.similarity_threshold` 设置的阈值，则返回 `true` 。
text <% text → boolean	单词匹配模式：第一个字符串连续部分的相似度超过 `pg_trgm.word_similarity_threshold` 设置的阈值，则返回 `true`。
text %> text → boolean	同上。第二个字符串连续部分的相似度超过 `pg_trgm.word_similarity_threshold` 设置的阈值，则返回 `true`。
text <<% text → boolean	严格单词匹配模式：第一个字符串相似度超过 `pg_trgm.strict_word_similarity_threshold` 设置的阈值，则返回 `true` 。
text %>> text → boolean	严格单词匹配模式：第二个字符串相似度超过 `pg_trgm.strict_word_similarity_threshold` 设置的阈值，则返回 `true` 。
text <-> text → real	字符串模式：两个字符串的非相似度。即 1 减去 `similarity()` 值。
text <<-> text → real	单词匹配模式下，两个字符串的非相似度。即 1 减去 `word_similarity()` 值。
text <->> text → real	同上。
`text` `<<<->` `text` → `real`	严格单词匹配模式: 两个字符串的非相似度。即 1 减去 `strict_word_similarity()` 值。
`text` `<->>>` `text` → `real`	同上。

1.4 查看三元组集合

SELECT show_trgm('words');
//屏幕输出：
 {"  w"," wo","ds ",ord,rds,wor}
(1 row)

2 pg_trgm的 GUC 参数

2.1 pg_trgm.similarity_threshold (real)

1、字符串匹配：设置字符串的相似度的阈值。该阈值必须位于0 和 1 之间。
2、默认为：0.3。

2.2 pg_trgm .word_similarity_threshold (real)

1、单词匹配模式：设置单词词相似度阈值。该阈值必须位于 0 和 1 之间。
2、默认为： 0.6。

2.3 pg_trgm .strict_word_similarity_threshold (real)

1、严格单词匹配模式：设置严格性单词相似性阈值。阈值必须介于0和1之间。
2、默认值为0.5。

3 pg_trgm 索引支持

关于索引操作符请参考 PostgreSQL SQL优化索引操作符。

3.1 索引操作符

1、pg_trgm 模块提供了 GiST 和 GIN 索引操作符类。
2、创建索引的字段必须为一个文本列（text ,varchar等）。
3、索引支持上述的相似度操作符。
4、额外支持 LIKE、ILIKE、~ 和 ~*and = 查询。
5、不支持不等式运算符。

Warning

请注意，这些索引可能不如常规B树索引的等值运算符高效。

3.2 索引操作符的匹配原理

1、有前缀的模糊查询，例如a％，至少需要提供1个字符。（搜索的是令牌='a'）
2、有后缀的模糊查询，例如％ab，至少需要提供2个字符。（搜索的是token ='ab'）
3、前后模糊查询，例如％abcd％，至少需要提供3个字符。（这个使用数组搜索，搜索的是token（s）包含{“a”，“ab”，abc，bcd，“cd”}）

3.3 索引操作符语法

1、语法定义。

CREATE INDEX trgm_idx ON test_trgm USING GIN (name gin_trgm_ops);

2、语法示例。

CREATE INDEX trgm_idx ON test_trgm USING GIST (t gist_trgm_ops(siglen=32));
CREATE INDEX trgm_idx ON test_trgm USING GIN (t gin_trgm_ops(siglen=32));

3.4 索引操作符语法说明

3、gist_trgm_ops 选项可以将一组三元组近似为一个标签。
4、标签长度由参数 siglen 确定（以字节为单位）。
5、标签默认长度为 12 个字节。
6、标签长度的有效值介于 1 到 2024 字节之间。
7、标签长度越长，提高搜索的精确度（扫描索引的一小部分和更少的堆页面），但代价是更大的索引。

4 pg_trgm 字符串的相似度

4.1 环境准备

准备两个字符串‘word’和‘words’两个字符串。

4.2 'word'字符串的三元组集合

5 个三元组。

 {"  w"," wo",ord,"rd ",wor}

4.3 'words'字符串的三元组集合

 {"  w"," wo","ds ",ord,rds,wor}

6个三元组。

4.4 similarity 比较字符串相似性

**计算公式：**将这两个三元组相比较，相似性计算为 6/(6 + 5)=0.54 ；

SELECT similarity('word', 'words');
//屏幕输出：
 similarity 
------------
  0.5714286
(1 row)

4.5 word_similarity 单词的相似性

**计算公式：**5/6 = 0.83333

SELECT word_similarity('word', 'words');
//屏幕输出：
 word_similarity 
-----------------
             0.8
(1 row)

4.6 strict_word_similarity 严格模式下的单词相似性

SELECT strict_word_similarity('word', 'words');
//屏幕输出：
 strict_word_similarity 
------------------------
              0.5714286
(1 row)

Warning

1、similarity 函数适合计算两个字符串的相似度。
2、word_similarity 更适合于计算单词的相似程度。
3、 strict_word_similarity 函数对于计算单词的完全匹配有用

5 pg_trgm 模糊查询示例

5.1 环境准备

CREATE TABLE test_trgm (id int ,name text);
INSERT INTO test_trgm SELECT oid,relname FROM pg_class;
CREATE INDEX trgm_idx ON test_trgm USING GIST (name gist_trgm_ops);

Note

或者：CREATE INDEX trgm_idx ON test_trgm USING GIN (name gin_trgm_ops);

5.2 字符串模式

5.2.1 相似度

1、当 name % 'payment' 低于 pg_trgm.similarity_threshold 时为 false。

SELECT name,similarity(name, 'payment') AS sml
  FROM test_trgm
  WHERE name % 'payment'
  ORDER BY sml DESC, name;
  //屏幕输出：
         name       |    sml     
------------------+------------
 city             |          1
 city_pkey        |        0.5
 city_city_id_seq | 0.41666666
 loc_city_ix      | 0.41666666
 idx_fk_city_id   |  0.3846154
(5 rows)

5.2.2 偏离度

SELECT name, 'payment' <-> name AS dist
  FROM test_trgm
  ORDER BY dist LIMIT 10;
//屏幕输出：
                name               |    dist    
----------------------------------+------------
 payment                          |          0
 payment_pkey                     |  0.3333333
 payment_payment_id_seq           | 0.46666664
 payment_p2007_04                 |        0.5
 payment_p2007_01                 |        0.5
 payment_p2007_05                 |        0.5
 payment_p2007_02                 |        0.5
 payment_p2007_06                 |        0.5
 payment_p2007_03                 |        0.5
 idx_fk_payment_p2007_03_staff_id | 0.73333335

Warning

这可以用 GiST 索引很高效地实现，但是用 GIN 索引不行。

5.2.3 执行计划

EXPLAIN SELECT name,similarity(name, 'payment') AS sml
FROM test_trgm
WHERE name % 'payment'
ORDER BY sml DESC, name;
QUERY PLAN                                    
---------------
 Sort  (cost=8.17..8.18 rows=1 width=23)
   Sort Key: (similarity(name, 'city'::text)) DESC, name
   ->  Index Scan using trgm_idx on test_trgm  (cost=0.14..8.16 rows=1 width=23)
         Index Cond: (name % 'city'::text)
(4 rows)

5.3 单词匹配模式

5.3.1 相似度

1、当 'payment' %> name 低于 pg_trgm.similarity_threshold 时为 false。

SELECT name,word_similarity(name, 'payment') AS sml
  FROM test_trgm
  WHERE 'payment' %> name
  ORDER BY sml DESC, name;
  //屏幕输出：
      name     |    sml    
--------------+-----------
 payment      |         1
 payment_pkey | 0.6666667
(2 rows)

5.3.2 偏离度

SELECT name, 'payment' <<-> name AS dist
  FROM test_trgm
  ORDER BY dist LIMIT 10;
//屏幕输出：
                name                 | dist 
-------------------------------------+------
 payment                             |    0
 payment_pkey                        |    0
 idx_fk_payment_p2007_01_staff_id    |    0
 idx_fk_payment_p2007_06_staff_id    |    0
 idx_fk_payment_p2007_06_customer_id |    0
 idx_fk_payment_p2007_05_staff_id    |    0
 idx_fk_payment_p2007_04_customer_id |    0
 payment_payment_id_seq              |    0
 payment_p2007_01                    |    0
 payment_p2007_04                    |    0
(10 rows)

Warning

这可以用 GiST 索引很高效地实现，但是用 GIN 索引不行。

5.3.3 执行计划

EXPLAIN SELECT name,word_similarity(name, 'payment') AS sml
  FROM test_trgm
  WHERE 'payment' %> name
  ORDER BY sml DESC, name;
 QUERY PLAN                            
-----------------------------------------------------------------
 Sort  (cost=10.72..10.73 rows=5 width=23)
   Sort Key: (word_similarity(name, 'payment'::text)) DESC, name
   ->  Seq Scan on test_trgm  (cost=0.00..10.66 rows=5 width=23)
         Filter: text %> name
(4 rows)

5.4 严格的单词匹配模式

5.4.1 相似度

1、当 'payment' %>> name 低于 pg_trgm.strict_word_similarity_threshold时为false 。

SELECT name,word_similarity(name, 'payment') AS sml
  FROM test_trgm
  WHERE 'payment'   %>> name
  ORDER BY sml DESC, name;
  //屏幕输出：
          name          |    sml     
------------------------+------------
 payment                |          1
 payment_pkey           |  0.6666667
 payment_payment_id_seq | 0.53333336
 payment_p2007_01       |        0.5
 payment_p2007_02       |        0.5
 payment_p2007_03       |        0.5
 payment_p2007_04       |        0.5
 payment_p2007_05       |        0.5
 payment_p2007_06       |        0.5
(9 rows)

5.4.2 偏离度

SELECT name, 'payment' <<<-> name AS dist
  FROM test_trgm
  ORDER BY dist LIMIT 10;
//屏幕输出：
                name                 | dist 
-------------------------------------+------
 payment                             |    0
 payment_pkey                        |    0
 idx_fk_payment_p2007_01_staff_id    |    0
 idx_fk_payment_p2007_06_staff_id    |    0
 idx_fk_payment_p2007_06_customer_id |    0
 idx_fk_payment_p2007_05_staff_id    |    0
 idx_fk_payment_p2007_04_customer_id |    0
 payment_payment_id_seq              |    0
 payment_p2007_01                    |    0
 payment_p2007_04                    |    0

Warning

这可以用 GiST 索引很高效地实现，但是用 GIN 索引不行。

5.4.3 执行计划

EXPLAIN SELECT name,word_similarity(name, 'payment') AS sml
  FROM test_trgm
  WHERE 'payment'   %>> name
  ORDER BY sml DESC, name;
  //屏幕输出：
QUERY PLAN                            
------------------------------------------------------------------
 Sort  (cost=10.87..10.90 rows=11 width=23)
   Sort Key: (word_similarity(name, 'payment'::text)) DESC, name
   ->  Seq Scan on test_trgm  (cost=0.00..10.68 rows=11 width=23)
         Filter: text %>> name
(4 rows)

5.5 正则表达式

5.5.1 相似度

SELECT * FROM test_trgm WHERE name ~ '(payment|film)';
//屏幕输出：
 id   |                name                 
-------+-------------------------------------
 16532 | film_film_id_seq
 16544 | film_actor
 16548 | film_category
 16588 | film_list
 16605 | nicer_but_slower_film_list
 16610 | payment_payment_id_seq
 16611 | payment
 16625 | payment_p2007_03
 16630 | payment_p2007_04
 16635 | payment_p2007_05
 16640 | payment_p2007_06
 16615 | payment_p2007_01
 16620 | payment_p2007_02
 16651 | sales_by_film_category
 16701 | film_actor_pkey
 16703 | film_category_pkey
 16705 | film_pkey
 16711 | payment_pkey
 16719 | film_fulltext_idx
 16725 | idx_fk_film_id
 16729 | idx_fk_payment_p2007_01_customer_id
 16730 | idx_fk_payment_p2007_01_staff_id
 16731 | idx_fk_payment_p2007_02_customer_id
 16732 | idx_fk_payment_p2007_02_staff_id
 16733 | idx_fk_payment_p2007_03_customer_id
 16734 | idx_fk_payment_p2007_03_staff_id
 16735 | idx_fk_payment_p2007_04_customer_id
 16736 | idx_fk_payment_p2007_04_staff_id
 16737 | idx_fk_payment_p2007_05_customer_id
 16738 | idx_fk_payment_p2007_05_staff_id
 16739 | idx_fk_payment_p2007_06_customer_id
 16740 | idx_fk_payment_p2007_06_staff_id
 16744 | idx_store_id_film_id
 16533 | film
(34 rows)

5.5.2 执行计划

EXPLAIN SELECT * FROM test_trgm WHERE name ~ '(payment|film)';
//屏幕输出：
QUERY PLAN                               
------------------------------------------------------------------------
 Bitmap Heap Scan on test_trgm  (cost=4.44..8.91 rows=38 width=23)
   Recheck Cond: (name ~ 'text
   ->  Bitmap Index Scan on trgm_idx  (cost=0.00..4.43 rows=38 width=0)
         Index Cond: (name ~ 'text
(4 rows)

5.6 LIKE 和 ILIKE

1、GIST 索引搜索通过从搜索字符串中提取三元组并且在索引中查找它们来工作。
2、与 B-树的搜索不同，搜索字符串不需要是左锚定的。
3、对于 LIKE 和正则表达式搜索，没有可提取的三元组时，执行计划将退化成一个全索引扫描。

SELECT * FROM test_trgm WHERE name LIKE '%pay%';
//屏幕输出：
  id   |                name                 
-------+-------------------------------------
 16610 | payment_payment_id_seq
 16611 | payment
 16625 | payment_p2007_03
 16630 | payment_p2007_04
 16635 | payment_p2007_05
 16640 | payment_p2007_06
 16615 | payment_p2007_01
 16620 | payment_p2007_02
 16711 | payment_pkey
 16729 | idx_fk_payment_p2007_01_customer_id
 16730 | idx_fk_payment_p2007_01_staff_id
 16731 | idx_fk_payment_p2007_02_customer_id
 16732 | idx_fk_payment_p2007_02_staff_id
 16733 | idx_fk_payment_p2007_03_customer_id
 16734 | idx_fk_payment_p2007_03_staff_id
 16735 | idx_fk_payment_p2007_04_customer_id
 16736 | idx_fk_payment_p2007_04_staff_id
 16737 | idx_fk_payment_p2007_05_customer_id
 16738 | idx_fk_payment_p2007_05_staff_id
 16739 | idx_fk_payment_p2007_06_customer_id
 16740 | idx_fk_payment_p2007_06_staff_id
(21 rows)

5.6.1 执行计划

EXPLAIN SELECT * FROM test_trgm WHERE name LIKE '%pay%';
//屏幕输出：
                               QUERY PLAN                               
------------------------------------------------------------------------
 Bitmap Heap Scan on test_trgm  (cost=4.31..8.57 rows=21 width=23)
   Recheck Cond: (name ~~ '%pay%'::text)
   ->  Bitmap Index Scan on trgm_idx  (cost=0.00..4.30 rows=21 width=0)
         Index Cond: (name ~~ '%pay%'::text)
(4 rows)

6 pg_trgm 索引操作符

使用请参考 PostgreSQL LIKE无法使用索引

7 参考连接

GiST 开发站点
 Tsearch2 开发站点